package com.test.demo.algorithm.sort;

public class SelectSort {

    /**
     * 选择排序
     * 两次循环，第二次循环分别跟第一次循环的当前的数比较，如果比第一次当前数小则交换位置
     * 现象：依次找到最小的数放到最左边
     * 13s
     * @param array
     * @return
     */
    public static int[] selectSort(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[i]) {
                    int temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                    count++;
                }
            }
        }
        //System.out.println("交换次数:" + count);
        return array;
    }

    /**
     * 进行优化
     * 减少交换次数
     * 4s
     * @param array
     * @return
     */
    public static int[] selectSort2(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            int min = i; //添加一个中间变量，记录本次遍历的最小值
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }

            }
            //最小值变化了再交换
            if (min != i) {
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
                count++;
            }
        }
        //System.out.println("交换次数:" + count);
        return array;
    }
}
